"""
希尔排序：O(n(logn)^2) or O(nlogn)
"""


def shell_sort(sequence):
    gap = len(sequence)
    while gap > 1:
        gap = gap // 2
        for i in range(gap, len(sequence)):
            for j in range(i % gap, i, gap):
                if sequence[i] < sequence[j]:
                    sequence[i], sequence[j] = sequence[j], sequence[i]
    return sequence


if __name__ == '__main__':
    sequence = [12, 27, 46, 16, 25, 37, 22, 29, 15, 47, 48, 34]
    print(sequence)
    print(shell_sort(sequence))
